package 剑指offer第2版;

public class 剑指Offer12矩阵中的路径 {

    /***
     * ###  矩阵中的路径（ DFS + 剪枝 ，清晰图解）
     * - 深度优先搜索
     * - 剪枝，`这条路不可能和目标字符串匹配成功`
     * - DFS解析
     * 	- 递归参数
     * 		- `当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k`
     * 	- 终止条件
     * 		- 返回false：
     * 			- 1，行或列索引越界
     * 			- 2，当前矩阵元素与目标字符不同
     * 			- 3，当前矩阵元素已访问过
     * 	- 递推工作
     * 		- 1，标记当前矩阵元素：将board[i][j]修改为空字符''，代表此元素已访问过，防止之后搜索时重复访问
     * 		- 2，搜索下一个单元格：朝当前元素的上，下，左，右四个方向开启下层递归，使用或连接（代表只需要找到一条可行路径就直接返回，不再做后续DFS），并记录结果至res
     * 		- 3，还原当前矩阵元素：将board[i][j]元素还原至初始值，即work[k]
     * 	- 返回值：返回布尔量res，代表是否搜索到目标字符串
     * @param board
     * @param word
     * @return
     */
    public  boolean exist(char[][] board, String word) {
        char[] chars = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(dfs(board,chars,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }

    public  boolean dfs(char[][] board,char[] word,int i,int j,int k){
        //边界处理，上下左右不能越界
        //终止条件,矩阵中元素等于k位置的字符,如果递归中矩阵中元素跟对应的字符不相等则直接返回false
        if( i<0 || j<0 || i > board.length-1 || j > board[0].length-1 || board[i][j]!=word[k]){
            return false;
        }
        if(k==word.length-1){
            return true;
        }
        //当前矩阵元素已访问过
        char tmp=board[i][j];
        board[i][j]='.';
        boolean dfs=false;
        //行++向下
        dfs |= dfs(board,word,i+1, j, k + 1);
        //行--向上
        dfs |=dfs(board,word,i-1,j,k+1);
        //列++向右
        dfs |= dfs(board,word, i, j+1, k + 1);
        //列--向左
        dfs |=dfs(board,word,i,j-1,k+1);
        board[i][j]=tmp;
        return dfs;
    }

    public static void main(String[] args) {


    }

    public static boolean test1(){
        return t1()||t2()||t3()||t4();
    }
    public static boolean test2(){
        boolean falg=false;
                falg|=t1();
                falg|=t2();
                falg|=t3();
                falg|=t4();
        return falg;
    }

    public static boolean t1(){
        System.out.println("t1");
        return false;
    }
    public static boolean t2(){
        System.out.println("t1");
        return true;
    }
    public static boolean t3(){
        System.out.println("t1");
        return true;
    }
    public static boolean t4(){
        System.out.println("t1");
        return true;
    }
}
